package practice_2025_8_28;

import java.util.ArrayList;
import java.util.Stack;

class Solution {

    /**
     * 用于控制序列化兼容性，验证类版本一致性的唯一标识符
     */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空数组，用于 new ArrayList(0)
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 空数组，用于无参构造
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *  存储元素的数组
     */
    transient Object[] elementData;

    /**
     * 实际元素个数
     */
    private int size;

    /**
     * 修改次数（用于 fail-fast 机制）
     */
    protected transient int modCount = 0;

    /**
     * 不同路径II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        dp[0][1] = 1;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 最长有效括号
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        //dp[i]: 以 i 结尾的最长有效括号长度
        // 当以 ) 结尾时，才有可能组成有效括号
        // 当s[i] = ( 时，入栈
        // 当 s[i] = ) 时，出栈 (，此时匹配一个 ( (j下标)，
        // (|j () )|i -> 说明中间都匹配了, i - j + 1
        // 还需要再加上之前的长度 dp[j - 1]
        Stack<Integer> stack = new Stack<>();
        int[] dp = new int[s.length()];
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    int left = stack.pop();
                    dp[i] += i - left + 1;
                    // 加上之前的长度
                    if (left > 0) {
                        dp[i] += dp[left - 1];
                    }
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }
}